package com.fengye.algorithms.alibaba;

import java.util.*;

/**
 * 有向无环图的DeepCopy
 * @Author fengye
 * @Date 2023/4/6 10:46
 **/
public class DAGDeepCopyMain {

    public static void main(String[] args) {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        node2.addEdge(node3);
        node2.addEdge(node4);
        node1.addEdge(node5);
        node1.addEdge(node2);
        node6.addEdge(node2);

        List<Node> nodes = new ArrayList<>();
        nodes.add(node1);
        nodes.add(node2);
        nodes.add(node3);
        nodes.add(node4);
        nodes.add(node5);
        nodes.add(node6);

        Collection<Node> newNodes = DeepCopy(nodes);

        newNodes.stream().forEach(System.out::println);
    }

    public static Collection<Node> DeepCopy(Collection<Node> nodes) {
        Collection<Node> newNodes = new ArrayList<>();
        Map<Node, Node> copyMap = new HashMap<>();
        for (Node node : nodes) {
            newNodes.add(copyNode(node, copyMap));
        }
        return newNodes;
    }
    private static Node copyNode(Node node, Map<Node, Node> copyMap) {
        if (copyMap.containsKey(node)) {
            return copyMap.get(node);
        }
        Collection<Node> newNeighbors = new ArrayList<>();
        for (Node neighbor : node.getNeighbors()) {
            newNeighbors.add(copyNode(neighbor, copyMap));
        }
        Node newNode = new Node(node.getValue(), newNeighbors);
        copyMap.put(node, newNode);
        return newNode;
    }

    static class Node{
        int value;

        Collection<Node> neighbors;

        public Node(int value) {
            this.value = value;
            this.neighbors = new ArrayList<>();
        }

        public Node(int value, Collection<Node> neighbors){
            this.value = value;
            this.neighbors = neighbors;
        }

        public void addEdge(Node node) {
            neighbors.add(node);
        }

        public int getValue() {
            return value;
        }

        public void setValue(int value) {
            this.value = value;
        }

        public Collection<Node> getNeighbors() {
            return neighbors;
        }

        public void setNeighbors(Collection<Node> neighbors) {
            this.neighbors = neighbors;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "value=" + value +
                    ", neighbors=" + neighbors +
                    '}';
        }
    }
}

